{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove All Ones With Row and Column Flips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeOnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过翻转行或列来去除所有的 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为&nbsp;<code>m x n</code> 的二进制矩阵&nbsp;<code>grid</code>。</p>\n",
    "\n",
    "<p>每次操作，你可以选择 <strong>任意</strong> 一行 或者 一列，然后将其中的所有值翻转（<code>0</code> 变成 <code>1</code>， <code>1</code>变成 <code>0</code>）。</p>\n",
    "\n",
    "<p>如果经过 <strong>任意次</strong> 操作，你能将矩阵中所有的 <code>1</code> 去除，那么返回 <code>true</code>；否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/01/03/image-20220103191300-1.png\" style=\"width: 756px; height: 225px;\">\n",
    "<pre><strong>输入:</strong> grid = [[0,1,0],[1,0,1],[0,1,0]]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 一种去除所有 1 的可行方法是:\n",
    "- 翻转矩阵的中间的行\n",
    "- 翻转矩阵的中间的列\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/01/03/image-20220103181204-7.png\" style=\"width: 237px; height: 225px;\">\n",
    "<pre><strong>输入:</strong> grid = [[1,1,0],[0,0,0],[0,0,0]]\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释:</strong> 不可能去除矩阵中所有的 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/01/03/image-20220103181224-8.png\" style=\"width: 114px; height: 100px;\">\n",
    "<pre><strong>输入:</strong> grid = [[0]]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 矩阵中不存在 1，已经符合要求。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 300</code></li>\n",
    "\t<li><code>grid[i][j]</code> 是&nbsp;<code>0</code>&nbsp;或者&nbsp;<code>1</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-all-ones-with-row-and-column-flips](https://leetcode.cn/problems/remove-all-ones-with-row-and-column-flips/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-all-ones-with-row-and-column-flips](https://leetcode.cn/problems/remove-all-ones-with-row-and-column-flips/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,0],[1,0,1],[0,1,0]]', '[[1,1,0],[0,0,0],[0,0,0]]', '[[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> int:\n",
    "        queue = collections.deque()\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        queue.append([grid,0])\n",
    "        while queue:\n",
    "            cur,step = queue.popleft()\n",
    "            flag = 1\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if cur[i][j]:\n",
    "                        flag = 0\n",
    "                        break\n",
    "                if not flag:\n",
    "                    break\n",
    "            if flag:\n",
    "                return step\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if cur[i][j]:\n",
    "                        temp = copy.deepcopy(cur)\n",
    "                        for k in range(m):\n",
    "                            if cur[i][k]:\n",
    "                                temp[i][k] = 0\n",
    "                        for k in range(n):\n",
    "                            if cur[k][j]:\n",
    "                                temp[k][j] = 0\n",
    "                        queue.append([temp,step + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def check_zero(grid):\n",
    "            for i in grid:\n",
    "                for j in i:\n",
    "                    if j == 1:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def get_min(grid):\n",
    "            if check_zero(grid):\n",
    "                return 0\n",
    "            ret = math.inf\n",
    "            for k,v in enumerate(grid):\n",
    "                for k2, v2 in enumerate(v):\n",
    "                    if v2 == 1:\n",
    "                        newc = deepcopy(grid)\n",
    "                        for k1, vv1 in enumerate(newc):\n",
    "                            for kk2, vv2 in enumerate(vv1):\n",
    "                                if k1 == k or kk2 == k2:\n",
    "                                    newc[k1][kk2] = 0\n",
    "                        ans1 = 1 + get_min(newc)\n",
    "                        ret = min(ret, ans1)\n",
    "            return ret\n",
    "\n",
    "\n",
    "        return get_min(grid)\n",
    "\n",
    "a = Solution()\n",
    "print(a.removeOnes([[1,1,1],[1,1,1],[0,1,0]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if not state:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for i in range(m * n):\n",
    "                if (1 << i) & state:\n",
    "                    row, col = divmod(i, n)\n",
    "                    nxt_state = state\n",
    "                    for r in range(m):\n",
    "                        if (b:= 1 << (r * n + col)) & nxt_state:\n",
    "                            nxt_state ^= b\n",
    "                    for c in range(n):\n",
    "                        if (b:= 1 << (row * n + c)) & nxt_state:\n",
    "                            nxt_state ^= b\n",
    "                    ans = min(ans, dfs(nxt_state))\n",
    "            return ans + 1\n",
    "        \n",
    "        return dfs(sum(1 << (i * n + j) if grid[i][j] else 0 for i in range(m) for j in range(n)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(1, m):\n",
    "            all_same, all_opposite = True, True\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != grid[0][j]:\n",
    "                    all_same = False\n",
    "                else:\n",
    "                    all_opposite = False\n",
    "                if not all_same and not all_opposite:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        xor = [x ^ 1 for x in grid[0]]\n",
    "        return all(row in (grid[0], xor) for row in grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      for i in range(1, m):\n",
    "        flag = grid[0][0] ^ grid[i][0]\n",
    "        for j in range(1, n):\n",
    "          if grid[i][j] ^ flag != grid[0][j]:\n",
    "            return False\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        tot = grid[0]\n",
    "        def check(x, y):\n",
    "            return all(x[i] == y[i] for i in range(len(x)))\n",
    "\n",
    "        for i in range(1, len(grid)):\n",
    "            arr = grid[i]\n",
    "            if not check(arr, tot):\n",
    "                for j in range(len(arr)):\n",
    "                    arr[j] = 0 if arr[j] else 1\n",
    "                if not check(arr, tot):\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        first_row = grid[0]\n",
    "        first_row_rev = []\n",
    "\n",
    "        for ele in first_row:\n",
    "            first_row_rev.append(ele^1)\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            if grid[i] != first_row and grid[i] != first_row_rev:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        # 记录每行的状态\n",
    "        states = set()\n",
    "        for row in grid:\n",
    "            cur = []\n",
    "            for num in row:\n",
    "                cur.append(str(num ^ row[0]))\n",
    "            states.add(''.join(cur))\n",
    "        print(states)\n",
    "        return len(states) == 1 # 如果只有一种状态，哪就是ok\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 位运算\n",
    "    # 与行首异或记录每行的状态 只需要判断下面每一行是否跟第一行相等\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        states = set()\n",
    "        for row in grid:\n",
    "            cur = []\n",
    "            for num in row:\n",
    "                cur.append(str(num ^ row[0]))\n",
    "\n",
    "            states.add(''.join(cur))\n",
    "\n",
    "        return len(states) == 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        #行和列等价\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(1,m):\n",
    "            flag=grid[i][0]==grid[0][0]\n",
    "            if flag:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]!=grid[0][j]: return False\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]^grid[0][j]!=1: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        #行和列等价\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(1,m):\n",
    "            flag=grid[i][0]==grid[0][0]\n",
    "            if flag:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]!=grid[0][j]: return False\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]^grid[0][j]!=1: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        for i in range(1, len(grid)):\n",
    "            f = 0\n",
    "            if grid[i][0] != grid[0][0]:\n",
    "                f = 1\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] ^ f != grid[0][j]:\n",
    "                    return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        states = set()  # 与行首异或, 记录每行的状态\n",
    "        for row in grid:\n",
    "            cur = []\n",
    "            for num in row:\n",
    "                cur.append(str(num ^ row[0])) # 每个数与行首异或\n",
    "            states.add(''.join(cur))\n",
    "        return len(states) == 1 # 如果每行的状态都一样，则可变"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        def check(x,y):\n",
    "            if x==y:\n",
    "                return True\n",
    "            for i in range(len(x)):\n",
    "                if x[i]==y[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        lst=[''.join(map(str,i))for i in grid]\n",
    "        for i in range(1,len(lst)):\n",
    "            if not check(lst[0],lst[i]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        def check(x,y):\n",
    "            if x==y:\n",
    "                return True\n",
    "            for i in range(len(x)):\n",
    "                if x[i]==y[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        lst=[''.join(map(str,i))for i in grid]\n",
    "        for i in range(1,len(lst)):\n",
    "            if not check(lst[0],lst[i]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> bool:\n",
    "        def check(x,y):\n",
    "            if x==y:\n",
    "                return True\n",
    "            for i in range(len(x)):\n",
    "                if x[i]==y[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        lst=[''.join(map(str,i))for i in grid]\n",
    "        for i in range(1,len(lst)):\n",
    "            if not check(lst[0],lst[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
